package leetcode.top100.Code39_40组合问题;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的数字可以无限制重复被选取。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1:
 * <p>
 * 输入: candidates = [2,3,6,7], target = 7,
 * 所求解集为:
 * [
 * [7],
 * [2,2,3]
 * ]
 * 示例 2:
 * <p>
 * 输入: candidates = [2,3,5], target = 8,
 * 所求解集为:
 * [
 *   [2,2,2,2],
 *   [2,3,3],
 *   [3,5]
 * ]
 * <p>
 * 分析：可以看成背包完全问题。把target看成背包，candidates看成物品质量
 *
 * @date 2020/3/29 18:18
 */
public class Code39_组合总和_目标和 {
    //方式1：看成完全背包回溯
    public static List<List<Integer>> combinationSum1(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();
        List<Integer> list = new LinkedList<>();
        process1(candidates, target, 0, list, res);
        return res;
    }

    private static void process1(int[] candidates, int target, int index, List<Integer> list,
                                 List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        if (target < 0 || index >= candidates.length) return;

        //当前物品可以拿0-n件。
        for (int count = 0; count * candidates[index] <= target; count++) {
            for (int i = 0; i < count; i++) {
                list.add(candidates[index]);
            }
            process1(candidates, target - count * candidates[index], index + 1, list, res);
            for (int i = 0; i < count; i++) {
                list.remove(list.size() - 1);
            }
        }
    }

    //方式2：回溯。
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();
        List<Integer> list = new LinkedList<>();
        process2(candidates, target, 0, list, res);
        return res;
    }

    private static void process2(int[] candidates, int target, int index, List<Integer> list,
                                 List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        if (target < 0 || index >= candidates.length) return;
        //对当前i一直下去，不往前走，如果往前走，i从0开始
        for (int i = index; i < candidates.length; i++) {
            list.add(candidates[i]);
            process2(candidates, target - candidates[i], i, list, res);
            list.remove(list.size() - 1);
        }

    }

    public static void main(String[] args) {
        int[] arr = {2, 2, 3, 6, 7};
        combinationSum1(arr, 7).forEach(System.out::println);
    }
}
